package com.cuz.hot100;

public class Q5longestPalindrome {
    public static String longestPalindrome1(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int start = 0;
        int end = 0;
        int maxLen = 0;
        char[] array = s.toCharArray();
        for (int index = 0; index < array.length; index++) {
            //index 作为中点，
            int temp1 = expend(array, index, index);
            // index 和index+1作为中点
            int temp2 = expend(array, index, index + 1);
            int max = Math.max(temp1, temp2);
            //更新长度 和最长的起点和结尾
            if (max > maxLen) {
                //假如是 acbabc  index=3 max=5  （5-1）/2=2 3-2=1 起点为1
                //如何是      acbaabc index=3 max=6 （6-1）/2=2 3-2=1 起点1
                start = index - (max - 1) / 2;
                //java subString 不包括末尾
                end = index + max / 2 + 1;
                maxLen = max;
            }
        }
        return s.substring(start, end);
    }

    /***
     * 中心扩展
     * @param array
     * @param i
     * @param j
     * @return
     */
    public static int expend(char[] array, int i, int j) {

        int len;
        //不越界 且相同
        if (i < array.length && j < array.length && array[i] == array[j]) {
            //偶数中心 那么为2 反之为1
            len = j - i + 1;
        } else {
            return 1;
        }
        i = i - 1;
        j = j + 1;
        //扩展
        while (i >= 0 && j < array.length && array[i] == array[j]) {
            i--;
            j++;
            len += 2;
        }
        return len;
    }

    public static void main(String[] args) {
        System.out.println(new Q5longestPalindrome()
                .longestPalindrome("babbad"));
    }


    public String longestPalindrome(String s) {
        if(s==null || s.length()==0){
            return "";
        }
        int maxStart = 0;
        int maxEnd = 0;

        for(int curIndex = 0 ; curIndex<s.length() ;curIndex++){
            int[] expendRes = expend(s,curIndex);
            int len = expendRes[0];

            if(len > maxEnd - maxStart + 1){
                maxStart = expendRes[1];
                maxEnd = expendRes[2];
            }
        }
        return s.substring(maxStart,maxEnd+1);
    }

    private int[]expend(String s,int index){
        int start1 = index-1;
        int end1 =index+1;

        int maxLen=1;
        if (start1>=0&&end1<s.length()&&s.charAt(start1)==s.charAt(end1)){
            while (start1-1>=0&&end1+1<s.length()&&s.charAt(start1-1)==s.charAt(end1+1)){
                start1--;
                end1++;
            }
        }else {
            start1=index;
            end1=index;
        }
        maxLen = Math.max(end1-start1+1,maxLen);

        int start2 = index;
        int end2 =index+1;
        if (start2>=0&&end2<s.length()&&s.charAt(start2)==s.charAt(end2)){
            while (start2-1>=0&&end2+1<s.length()&&s.charAt(start2-1)==s.charAt(end2+1)){
                start2--;
                end2++;
            }
        }else {
            start2=index;
            end2=index;
        }
        if (end2-start2+1>maxLen){
            return new int[]{end2-start2+1,start2,end2};
        }
        return new int[]{end1-start1+1,start1,end1};
    }
}
